from Base import *

# U(n), Multiplication mod n
class MultiModGroup(object):
    def __init__(self, modulo, items = []):
        assert type(modulo) == type(0) 
        self.modulo = modulo

        if len(items) == 0:
            self.identity = 1
            self.items = CoprimeSet(self.modulo)
        else:
            self.identity = None
            for item in items:
                if (item * item) % self.modulo == item:
                    self.identity = item
            assert self.identity

            self.items = items
   
    def Identity(self):
        return self.identity

    def Add(self, left, right):
        return (left + right) % self.modulo

    def Subtract(self, minuend, subtrahend):
        return (minuend - subtrahend) % self.modulo

    def Multiply(self, left, right):
        return (left * right) % self.modulo

    def Power(self, item, power):
        return (item ** power) % self.modulo

    def Inverse(self, input):
        assert input in self.items
        return BezoutIdentity(input, self.modulo)[1] % self.modulo

    # The order of multiplication group
    def Order(self):
        return len(self.items)

    # The order of the given element under multiplication group
    def ElementOrder(self, n, subgroup = []):
        assert type(n) == type(0) 
        maxOrder = self.Order()

        power = 1
        m = n
        while m != self.identity:
            m = self.Multiply(m, n)
            power += 1
            assert not power > maxOrder
            assert m in self.items
        return power

    def IsCyclic(self):
        generators = []
        order = self.Order()
        for item in self.items:
            if self.ElementOrder(item) == order:
                generators.append(item)
        return len(generators) > 0, generators
